package com.yun.datastructure.tree.redblacktree;


public class RedBlackTree {

    enum Color {
        RED, BLACK
    }

    private Node root;

    private static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;            //父节点
        Color color = Color.RED;  //颜色

        //是否是左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        //叔叔
        Node uncle() {
            if (parent == null || parent.parent == null) {
                return null;
            }
            if (parent.isLeftChild()) {
                return parent.parent.right;
            } else {
                return parent.parent.left;
            }
        }

        //兄弟
        Node sibling() {
            if (parent == null) {
                return null;
            }
            if (this.isLeftChild()) {
                return parent.right;
            } else {
                return parent.left;
            }
        }

        public Node(int key) {
            this.key = key;
        }

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    //判断红黑
    boolean isRed(Node node) {
        return node != null && node.color == Color.RED;
    }

    boolean isBlack(Node node) {
        return node == null || node.color == Color.BLACK;
    }

    //右旋
    private void rightRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.left;
        Node green = yellow.right;
        if (green != null) {
            green.parent = pink;
        }
        yellow.right = pink;
        yellow.parent = parent;
        pink.left = green;
        pink.parent = yellow;
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }

    private void leftRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.right;
        Node green = yellow.left;
        if (green != null) {
            green.parent = pink;
        }
        yellow.left = pink;
        yellow.parent = parent;
        pink.right = green;
        pink.parent = yellow;
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }

    /*
        红黑树特性
        1.所有节点都有两种颜色：红与黑
        2.所有null视为黑色
        3.红色节点不能相邻
        4.根节点是黑色
        5.从根到任意一个叶子节点，路径中黑色节点数一样（黑色完美平衡）
     */

    /*
     * 新增或更新
     * 正常增，遇到红红不平衡进行调整
     */
    public void put(int key, Object value) {
        Node p = root;
        Node parent = null;
        while (p != null) {
            parent = p;
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                p.value = value;
                return;
            }
        }
        Node inserted = new Node(key, value);
        if (parent == null) {
            root = inserted;
        } else if (key < parent.key) {
            parent.left = inserted;
            inserted.parent = parent;
        } else {
            parent.right = inserted;
            inserted.parent = parent;
        }
        fixRedRed(inserted);
    }

    /*
        插入节点均视为红色
        case1:插入节点为根节点，将根节点变为黑色
        case2：插入节点的父亲若为黑色，树的红黑性质不变，无需调整
        插入节点的父亲为红色，触发红红相邻
        case3：叔叔为红色
            1.父亲变为黑色，为了保证黑色平衡，连带着叔叔也要变成黑色
            2.如果祖父是黑色不变，会造成这棵子树黑色过多，因此祖父节点变成红色
            3.祖父如果变为红色，可能会触发红红相邻，因此对祖父进行递归调整
        case4：叔叔为黑色
     */
    private void fixRedRed(Node x) {
        //case 1 插入节点是根节点，变黑即可
        if (x == root) {
            x.color = Color.BLACK;
            return;
        }
        //case 2 插入节点父亲是黑色，无需调整
        if (isBlack(x.parent)) {
            return;
        }
        /* case 3 当红红相邻，叔叔为红时
            需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
         */
        Node parent = x.parent;
        Node uncle = x.uncle();
        Node grandparent = parent.parent;
        if (isRed(uncle)) {
            parent.color = Color.BLACK;
            uncle.color = Color.BLACK;
            grandparent.color = Color.RED;
            fixRedRed(grandparent);
            return;
        }
        //case 4 当红红相邻，叔叔为黑时
        if (parent.isLeftChild() && x.isLeftChild()) {//case4 LL
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        } else if (parent.isLeftChild()) {//case4 LR
            leftRotate(parent);
            x.color = Color.BLACK;
            grandparent.color = Color.RED;
            rightRotate(grandparent);
        } else if (!x.isLeftChild()) {//RR
            parent.color = Color.BLACK;
            grandparent.color = Color.RED;
            leftRotate(grandparent);
        } else {//RL
            rightRotate(parent);
            x.color = Color.BLACK;
            grandparent.color = Color.RED;
            leftRotate(grandparent);
        }
    }

    /*
     * 删除
     * 正常删，会用到李代桃僵技巧，遇到黑黑不平衡进行调整
     */
    /*
        case0:如果删除节点有2个孩子=>有一个孩子或没有孩子
            将待删除节点和其后继节点直接交换键和值，然后删除交换之后的待删除节点，
                重复执行该过程直到删除节点没有孩子或只有一个孩子。此时case0转换为其他情况。
        case1：删除的节点为根节点
            1.根节点没有孩子，直接根节点等于null
            2.根节点只有一个孩子
                1)根节点如果有2个孩子就会进入case0
                2)根节点只有一个孩子时，如果该孩子为黑色，
                    则这棵树不平衡，所以该子一定为红色
                3)此时可以将根节点和他的孩子交换键值，然后删除孩子，颜色保持不变
        case2：删除的节点不是根节点(删除节点为黑色会影响平衡，删除节点为红色不会影响平衡)
            删除的是黑节点，剩下的是红色，则让剩下的这个红节点变黑。
            1.删除的节点如果有2个孩子就会进入case0，
                所以此时删除节点只有一个孩子或没有孩子
            2.删除节点没有孩子
                1)拿到删除节点的父亲
                2)修改删除节点的父亲的孩子
                3)删除的节点为黑节点，剩下的节点为null，触发双黑，跳转到case3。
            3.删除节点有一个孩子
                1)拿到删除节点的父亲
                2)修改删除节点的父亲的孩子
                3)删除的节点为黑节点，剩下的节点为红节点，进入情况case2，将剩下的红节点变黑
                4)删除的节点为黑节点，剩下的节点为黑节点，触发双黑，跳转到case3。
        双黑情况，fixDoubleBlack(case3,4,5)
        case3:待调整的节点的兄弟为红，则待调整节点的父亲必定为黑，并且两个侄子必定为黑
            此时对待调整的节点的父亲进行一次旋转，然后将原父亲节点和原兄弟节点交换颜色
            此时待调整的节点的新兄弟一定为黑色，进入case4或case5
        case4：待调整的节点的兄弟为黑色，两个侄子都为黑
            1.将兄弟变红，目的是将删除节点和兄弟那边的黑色高度同时减少1
            2.如果父亲是红色，则需将父亲变黑，避免红红，此时路径黑节点数目不变
            3.如果父亲是黑色，说明这条路径则少了一个黑，再次让父节点触发双黑
        case5：待调整的节点的兄弟为黑色，至少一个侄子为红
            1.如果兄弟是左孩子，左侄子是红色，LL不平衡
            2.如果兄弟是右孩子，右侄子是红色，LR不平衡
            3.如果兄弟是左孩子，右侄子是红色，RR不平衡
            4.如果兄弟是左孩子，左侄子是红色，RL不平衡
     */
    public void remove(int key) {
        Node deleted = find(key);
        if (deleted == null) {
            return;
        }
        doRemove(deleted);
    }

    //查询删除节点
    private Node find(int key) {
        Node p = root;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

    private void doRemove(Node deleted) {
        Node replaced = findReplaced(deleted);
        Node parent = deleted.parent;
        if (replaced == null) {
            //case1
            if (deleted == root) {
                root = null;
            } else {
                if (isBlack(deleted)) {
                    //复杂处理
                    fixDoubleBlack(deleted);
                } //else 红色叶子，无需任何处理
                if (deleted.isLeftChild()) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                deleted.parent = null;
            }
            return;
        }
        //有一个孩子
        if (deleted.left == null || deleted.right == null) {
            //case1 删除的是根节点
            if (deleted == root) {
                root.key = replaced.key;
                root.value = replaced.value;
                root.left = root.right = null;
            } else {
                if (deleted.isLeftChild()) {
                    parent.left = replaced;
                } else {
                    parent.right = replaced;
                }
                replaced.parent = parent;
                deleted.left = deleted.right = deleted.parent = null;
                if (isBlack(deleted) && isBlack(replaced)) {
                    //复杂处理-实际不会有这种情况 因为只有一个孩子时 被删除节点时黑色 那么剩余节点只能是红色不会触发双黑
                    fixDoubleBlack(replaced);
                } else {
                    //case2
                    replaced.color = Color.BLACK;
                }
            }
            return;
        }
        //有两个孩子=>有一个孩子或没有孩子 case0
        int t = deleted.key;
        deleted.key = replaced.key;
        replaced.key = t;

        Object v = deleted.value;
        deleted.value = replaced.value;
        replaced.value = v;
        doRemove(replaced);
    }

    //查找剩余节点
    private Node findReplaced(Node deleted) {
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        Node s = deleted.right;
        while (s.left != null) {
            s = s.left;
        }
        return s;
    }

    private void fixDoubleBlack(Node x) {
        if (x == root) {
            return;
        }
        Node parent = x.parent;
        Node sibling = x.sibling();
        //case3 兄弟节点为红色
        if (isRed(sibling)) {
            if (x.isLeftChild()) {
                leftRotate(parent);
            } else {
                rightRotate(parent);
            }
            parent.color = Color.RED;
            sibling.color = Color.BLACK;
            fixDoubleBlack(x);
            return;
        }
        //case4 兄弟是黑色并且两个侄子也是黑色
        if (sibling != null) {
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                sibling.color = Color.RED;
                if (isRed(parent)) {
                    parent.color = Color.BLACK;
                } else {
                    fixDoubleBlack(parent);
                }
            }
            //case5 兄弟是黑色，侄子是红色
            else {
                //LL
                if (sibling.isLeftChild() && isRed(sibling.left)) {
                    sibling.left.color = Color.BLACK;
                    sibling.color = parent.color;
                    rightRotate(parent);
                }
                //LR
                else if (sibling.isLeftChild() && isRed(sibling.right)) {
                    sibling.right.color = parent.color;
                    leftRotate(sibling);
                    rightRotate(parent);
                }
                //RL
                else if (!sibling.isLeftChild() && isRed(sibling.left)) {
                    sibling.left.color = parent.color;
                    rightRotate(sibling);
                    leftRotate(parent);
                }
                //RR
                else if (!sibling.isLeftChild() && isRed(sibling.right)) {
                    sibling.right.color = Color.BLACK;
                    sibling.color = parent.color;
                    leftRotate(parent);
                }
                parent.color = Color.BLACK;
            }
        } else {
            //实际也不会出现，触发双黑后，兄弟节点不会为 null
            fixDoubleBlack(parent);
        }
    }
}
